import algo.tree.*;

class Main {
    public static void main (String[] args) {
        Integer[] nums = new Integer[]{1,2,3,35,234,261,34,8,74, 67,93, 349, 223, 40, 45,54,515,15,45,1,1,14,14,14,51,62, 1234,9478, 2,625,6};
        printArray(nums);
//        new Selection<Integer>().sort(nums);
//        new Bubble<Integer>().sortDesc(nums);
//        new Insertion<Integer>().sortDesc(nums);
//        new Shell<Integer>().sort(nums);  // 虽然希尔不如下面的排序算法，但速率也能达到下面的1/2左右

//        new Up2DownMergeSort<Integer>().sort(nums);
//        new Down2UpMergeSort<Integer>().sortDesc(nums);
//        new QuickSort<Integer>().sortDesc(nums);
//        new ThreeWayQuickSort<Integer>().sortDesc(nums);
//        System.out.println(new QuickSort<Integer>().selectKthBig(nums, 1));
//        new HeapSort<Integer>().sort(nums);
//        printArray(nums);

        // 红黑树：
        RedBlackTree<Integer> RBTree = new RedBlackTree<>();
//        RedBlackTreeMap<Integer, Integer> RBTreeMap = new RedBlackTreeMap<>();
        for (Integer num: nums) {
            System.out.print("adding: "+num);
            System.out.println("  "+RBTree.insert(num));
//            System.out.println("  "+RBTreeMap.insert(num, num+1000));
        }
        RBTree.printPreTraverse();
        RBTree.printMidTraverse();
        RBTree.printPostTraverse();
        RBTree.printLevelTraverse();
//        RBTreeMap.printPreTraverse();
//        RBTreeMap.printMidTraverse();
//        RBTreeMap.printPostTraverse();
//        RBTreeMap.printLevelTraverse();
        for (Integer num: nums) {
            System.out.println("deleting: "+num+"\t"+RBTree.delete(num));
        }
    }

    static void printArray(Integer[] nums) {
        for (int num: nums)
            System.out.print(num + " ");

        System.out.println();
    }
}